package com.dmall.algorithm.chapter01;

import java.util.ArrayList;
import java.util.List;

public class Leetcode22 {
    public List<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<>();
        _generate(0, 0, n, "", list);
        return list;
    }

    private void _generate(int left, int right, int n, String str, ArrayList<String> list) {
        if (left == n && right == n) {
            list.add(str);
            System.out.println(str);
            return;
        }

        if (left < n)
            _generate(left + 1, right, n, str + "(", list);
        if (left > right)
            _generate(left, right + 1, n, str + ")", list);
    }

    public static void main(String[] args) {
        Leetcode22 leetcode22 = new Leetcode22();
        leetcode22.generateParenthesis(3);
    }
}
